package slidingwindow;

import java.util.HashMap;
import java.util.Map;

public class solution76 {
    public static String minWindow(String s, String t) {
        /*记录一下滑动窗口中出现t中元素的次数*/
        Map<Character,Integer> windows = new HashMap<>();
        Map<Character,Integer> needs = new HashMap<>();

        int left = 0;
        int right = 0;
        /*valid记录windows中满足need条件的字符的个数，如果valid==need.size()，则说明window满足条件*/
        int valid = 0;

        int start=0;
        int length=Integer.MAX_VALUE;

        /*
        * 统计一下t中出现了哪些字符，并且这些字符出现了几次
        * */
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            needs.put(c,needs.getOrDefault(c,0)+1);
        }

        /*
        * 开始写框架
        * */
        while(right < s.length()){
            char c = s.charAt(right);
            right++;

            //更新数据，我们先判断一下是否要把当前的字符放入windows中统计
            if (needs.containsKey(c)){
                windows.put(c,windows.getOrDefault(c,0)+1);
                //needs中所要求的元素个数==windows中所拥有的元素个数
                //则valid++；
                if (windows.get(c).equals(needs.get(c))){
                    valid++;
                }
            }

            //while(window need shrink)
            //这道题中的缩小条件是window已经满足t的要求
            while(valid == needs.size()){

                /*原来报错是这个地方写错了
                * 我默认只要进了这个for循环，就把left赋值给start
                * 实际上进了这个循环的又不一定是最优解
                * */
               if (right-left<length){
                   start = left;
                   length = right-left;
               }

                char cRemove = s.charAt(left);
                left++;

                //依旧更新数据
                if (needs.containsKey(cRemove)){

                    //只有如下情况才需要将valid--；
                    //若windows.get(cRemove)<needs.get(cRemove)，这种情况已经没必要valid--了
                    if (windows.get(cRemove).equals(needs.get(cRemove))){
                        valid--;
                    }
                    windows.put(cRemove, windows.get(cRemove)-1);

                }
            }
        }

        return length==Integer.MAX_VALUE ? "":s.substring(start,start+length);

    }

    public static void main(String[] args) {
        String s = "cabwefgewcwaefgcf";
        String t = "cae";

        String minWindow = minWindow(s, t);

        System.out.println("minWindow = " + minWindow);

    }
}
